1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
| /**
* Description : 算法设计课，课后作业，利用C++ STL表示邻接链表，找出简单路径
* Date : 2015.03.11
* Author : knarfeh
* Version : 0.01
*/
#define NNUM 4
#include <iostream>
#include <string>
#include <list>
#include <array>
using namespace std;
class UnionDataList{
public:
UnionDataList(char data, int weight) :nodeChar(data), weightInt(weight) {}
char getNode() {
return nodeChar;
};
int getWeight() {
return weightInt;
};
private:
char nodeChar;
int weightInt;
};
list<UnionDataList> adjaList;
list<UnionDataList>::iterator iterForGetIndex, iterForPrint;
array<list<UnionDataList>, NNUM> adjaArray;
UnionDataList tempData('0', 0);
int visited[NNUM] = { 0 };
// 根据结点值返回邻接数组的下标值，如果没有返回-1
int getIndexByNode(array<list<UnionDataList>, NNUM> a, char c) {
for (unsigned int i = 0; i < a.max_size(); i++) {
iterForGetIndex = a[i].begin();
if ((*iterForGetIndex).getNode() == c) {
return i;
}
}
return -1;
}
// 输出邻接链表
void dispAdjaList(array<list<UnionDataList>, NNUM> a) {
UnionDataList tempDataForDisp('0', 0);
// cout << a.max_size() << endl;
for (unsigned int i = 0; i < a.max_size(); i++) {
for (iterForPrint = a[i].begin(); iterForPrint != a[i].end(); iterForPrint++) {
if (iterForPrint == a[i].begin()) { // 邻接链表的第一个值
cout << "[" << i << "," << (*iterForPrint).getNode() << "]";
}
else {
cout << "(" << (*iterForPrint).getNode() << "," << (*iterForPrint).getWeight() << ")";
}
cout << "->";
}
cout << "^" << endl;
}
}
// 输出nodeA到nodeB的所有简单路径
void printPathAll(array<list<UnionDataList>, NNUM> a, char nodeA, char nodeB, char path[], int pathNum){
int nowIndex = getIndexByNode(a, nodeA);
visited[nowIndex] = 1;
path[pathNum++] = nodeA;
if (nodeA == nodeB) {
int i;
for (i = 0; i < pathNum - 1; i++) {
cout << path[i] << "->";
}
cout << path[i] << endl;
}
list<UnionDataList>::iterator iterForPrintAll;
for (iterForPrintAll = a[nowIndex].begin(); iterForPrintAll != a[nowIndex].end(); iterForPrintAll++) {
if (0 == visited[getIndexByNode(a, (*iterForPrintAll).getNode())]) { // 没有访问过
printPathAll(a, (*iterForPrintAll).getNode(), nodeB, path, pathNum);
}
}
visited[nowIndex] = 0;
pathNum--;
}
int main(int argc, char *argv[]){
//list<Mydata> mylist;
UnionDataList nowData('a', 0);
// mylist.push_back({ 'c', 1 });
//nowData = mylist.front();
//cout << nowData.getNode() << endl;
//cout << nowData.getWeight() << endl;
adjaArray[0].push_back({ 'a', 0 });
adjaArray[0].push_back({ 'b', 5 });
adjaArray[0].push_back({ 'c', 1 });
adjaArray[1].push_back({ 'b', 0 });
adjaArray[1].push_back({ 'a', 5 });
adjaArray[1].push_back({ 'c', 7 });
adjaArray[1].push_back({ 'd', 4 });
adjaArray[2].push_back({ 'c', 0 });
adjaArray[2].push_back({ 'a', 1 });
adjaArray[2].push_back({ 'b', 7 });
adjaArray[2].push_back({ 'd', 2 });
adjaArray[3].push_back({ 'd', 0 });
adjaArray[3].push_back({ 'b', 4 });
adjaArray[3].push_back({ 'c', 2 });
cout << "邻接链表为：" << endl;
dispAdjaList(adjaArray);
cout << endl;
// cout << getIndexByNode(adjaArray, 'c');
char path2Print[NNUM];
int pathNum = 0;
cout << "所有的简单路径：" << endl;
printPathAll(adjaArray, 'a', 'd', path2Print, pathNum);
}
|
